package org.xtlgen;

import java.awt.geom.Point2D;
import java.util.Comparator;
import java.util.HashSet;
import java.util.TreeSet;
import java.util.HashMap;
import java.util.Set;

/**
 * Encapsulates the Voronoi algorithm.
 */
public class VoronoiGenerator {
  private DelaunayTriangulation dt;     // The Delaunay triangulation
  private Simplex<Pnt> initialTriangle; // The large initial triangle
  private HashMap<Pnt, Set<Polygon.Vertice>> verticesForPoint;

  /**
   * Create and initialize the DelaunayTriangulation.
   * The given bounds are used to calculate the size of the initial rectangle
   * required for the given points.
   */
  public VoronoiGenerator (double minX, double minY, double maxX, double maxY) {
    // Calculate the size of the initial triangle
    double initialSize = Math.max(Math.abs(maxX - minX),
                                  Math.abs(maxY - minY)) * 10.0;
    
    initialTriangle =
      new Simplex<Pnt>(
        new Pnt(-initialSize + minX, -initialSize + minY),
        new Pnt( initialSize + minX, -initialSize + minY),
        new Pnt(               minX,  initialSize + minY));
    dt = new DelaunayTriangulation(initialTriangle);
    verticesForPoint = null;
  }
    
  /**
   * Add one point to the triangulation.
   * @param p the point to add.
   */
  public void addPoint (Point p) {
    Pnt point = new Pnt(p.getX(), p.getY());
    dt.delaunayPlace(point);
    // Throw away old point data if present
    verticesForPoint = null;
  }

  /**
   * Get a set of Polygon.Vertices for the polygon around the given Point
   * @param p the Point for which to get the vertices.
   * @return the set of vertices.
   */
  public Set<Polygon.Vertice> getVertices (Point p) {
    Pnt point = new Pnt(p.getX(), p.getY());
    if (verticesForPoint == null) {
      calcVoronoiEdges();
    }
    return verticesForPoint.get(point);
  }

  /*
   * Calculate all the Voronoi edges.
   */
  private void calcVoronoiEdges () {
    // Maps a vertice to all triangle facets containing it
    HashMap<Pnt,HashSet<Set<Pnt>>> facetsOnVertice =
      new HashMap<Pnt,HashSet<Set<Pnt>>>();
    // Maps each triangle line to the corresponding Voronoi edge line
    HashMap<Set<Pnt>,Set<Polygon.Vertice>> vorEdges =
      new HashMap<Set<Pnt>,Set<Polygon.Vertice>>();
    
    // Loop through all the edges of the DT (each is done twice)
    for (Simplex<Pnt> triangle: dt) {

      // Update the point to facet map for each of this triangle's facets
      for (Set<Pnt> facet : triangle.facets()) {
        for (Pnt p : facet) {
          HashSet<Set<Pnt>> facets;
          if (facetsOnVertice.containsKey(p)) {
            facets = facetsOnVertice.get(p);
          }
          else {
            facets = new HashSet<Set<Pnt>>();
            facetsOnVertice.put(p, facets);
          }
          facets.add(facet);
        }
      }

      // Obtain the two coordinates for each edge
      for (Simplex<Pnt> other: dt.neighbors(triangle)) {
        Pnt p = Pnt.circumcenter(triangle.toArray(new Pnt[0]));
        Pnt q = Pnt.circumcenter(other.toArray(new Pnt[0]));
 
        // Get the common facet and associate with the line
        HashSet<Polygon.Vertice> edge = new HashSet<Polygon.Vertice>();
        edge.add(new Polygon.Vertice(p.coord(0), p.coord(1)));
        edge.add(new Polygon.Vertice(q.coord(0), q.coord(1)));
        vorEdges.put(triangle.commonFacet(other), edge);
      }
    }

    verticesForPoint = new HashMap<Pnt, Set<Polygon.Vertice>>();

    for (Pnt p : facetsOnVertice.keySet()) {
      HashSet<Set<Pnt>> facets = facetsOnVertice.get(p);
      TreeSet<Polygon.Vertice> polyPoints =
        new TreeSet<Polygon.Vertice>(
          new VerticeComparator(new Polygon.Vertice(p.coord(0), p.coord(1))));
      for (Set<Pnt> facet : facets) {
        Set<Polygon.Vertice> edge = vorEdges.get(facet);
        if (edge != null) {
          polyPoints.addAll(edge);
        }
      }
      verticesForPoint.put(p, polyPoints);
    }
  }

  /*
   * Nested class that implemements a Comparator for Polygon.Vertices.
   * The vertices are sorted according to an angle calculated creating a line
   * from the supplied center vertice to each of the vertices.
   */
  private static class VerticeComparator implements Comparator<Polygon.Vertice> {
    /*
     * Creates a VerticeComparator with the given center vertice.
     */
    public VerticeComparator(Polygon.Vertice center) {
      this.center = center;
    }

    /*
     * Compare the two points given.
     */
    public int compare(Polygon.Vertice p1, Polygon.Vertice p2) {
      double a1 = calcAngle(p1.getX()-center.getX(), p1.getY()-center.getY());
      double a2 = calcAngle(p2.getX()-center.getX(), p2.getY()-center.getY());
      double diff = a2-a1;
      return ((diff == 0) ? 0 : ((diff < 0) ? -1 : 1));
    }

    /*
     * Return true of this object is equal to the given object.
     */
    public boolean equals(Object other) {
      if (!(other instanceof VerticeComparator)) {
        return false;
      }

      return this.center.equals(((VerticeComparator)other).center);
    }
    
    /*
     * Calculate an angle from the given horizontal and vertical distances.
     */
    private double calcAngle(double xDist, double vDist) {
      double angle = 0;
      if (xDist < 0) {
        angle = 180;
      }
      angle += Math.toDegrees(Math.atan(vDist/xDist));
      if (angle > 180) {
        angle -= 360;
      }
      return angle;
    }

    /*
     * Fields.
     */
    private Polygon.Vertice center;
  }
}
 